package org.leetcode.middle.leetcode300;

import java.util.Arrays;

public class Solution {

    public int lengthOfLIS3(int[] nums) {

        int maxLength = 1;

        int n = nums.length;

        int [] dp = new int[n];

        Arrays.fill(dp,1);

        for (int i = 1; i < n; i++) {
            for (int j = 0; j <i; j++) {
                if (nums[i]>nums[j]){
                    dp[i]= Math.max(dp[i],dp[j]+1);
                }
            }
            maxLength=Math.max(maxLength,dp[i]);
        }

        return maxLength;
    }

    public int lengthOfLIS2(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        int res = 0;

        for (int i = 1; i < dp.length; i++) {
            for (int j = 0; j <= i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            res = Math.max(dp[i], res);
        }
        return res;
    }

    public int lengthOfLIS(int[] nums) {

        //dp[i]的含义：以num[i]为结尾的最长子序列。如：nums={10,9,2,5,3,7,101,18}。dp[3]表示nums[3]=5为结尾的最大子序列长度为2。
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        int result = 1;

        for (int i = 1; i < dp.length; i++) {
            //遍历0到i中的最长子序列
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    //这里不是要dp[i] 与 dp[j] + 1进行比较，而是我们要取dp[j] + 1的最大值
                    //比如最开始dp[i]=1，随着后续的对比，dp[i]=3,那么需要判断还有没有比3还长的子序列
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            result = Math.max(result, dp[i]);
        }

//        for (int maxLength:dp) {
//            result=Math.max(result,maxLength);
//        }

        return result;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        int res = solution.lengthOfLIS(nums);
        System.out.println(res);
    }
}
